#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

class Solution {
    public:
	int electricCarPlan(vector<vector<int>> &paths, int cnt, int start, int end, vector<int> &charge)
	{
                int n = charge.size();
                vector<vector<vector<int>>> gh(n);
                for(auto e : paths){
                        int u = e[0], v = e[1], c = e[2];
                        gh[u].push_back({v, c});
                        gh[v].push_back({u, c});
                }
                vector<vector<int>> dis(n, vector<int>(cnt + 1, INT32_MAX));
                vector<vector<int>> vis(n, vector<int>(cnt + 1, 0));

                dis[start][0] = 0;
                priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
                pq.emplace(0, start, 0);

                while(!pq.empty()){
                        auto [cost, u, power] = pq.top();
                        pq.pop();

                        if(vis[u][power]){
                                continue;
                        }
                        vis[u][power] = 1;

                        if(u == end){
                                return cost;
                        }

                        if(power < cnt){
                                int c = cost + charge[u];
                                int p = power + 1;
                                if(!vis[u][p]){
                                        pq.emplace(c, u, p);
                                }
                        }

                        for(auto e : gh[u]){
                                int v = e[0], cv = e[1];
                                int p = power - cv;
                                int c = cost + cv;
                                if(p >= 0 && c < dis[v][p] && !vis[v][p]){
                                        dis[v][p] = c;
                                        pq.emplace(c, v, p);
                                }
                        }
                }
                return -1;
	}
};

int main()
{
	vector<vector<int>> paths = { { 1, 3, 3 }, { 3, 2, 1 }, { 2, 1, 3 }, { 0, 1, 4 }, { 3, 0, 5 } };
	int cnt = 6, start = 1, end = 0;
	vector<int> charge = { 2, 10, 4, 1 };
        cout<<Solution().electricCarPlan(paths, cnt, start, end, charge)<<endl;
	return 0;
}